package day09;

public class MyLinkedList {
	private Node head = new Node();//	头节点，next = null
	private int size = 0;//	有效节点个数
	
	/**
	 *	节点类就是为了MyLinkedList来服务的，所以定义成内部类
	 *	节点中包含两部分：保存数据用的date，指向下一个节点的next
	 */
	private class Node{
		private Object date; //	储存数据
		private Node next; //	保存下一个节点的引用
	}
	//	完成的方法参考MyArrayList
	/**	向集合(this)的末尾中添加元素*/
	public void add(Object obj) {
		//	只能从头开始，找到链表的末尾
		Node node = head;
		while (node.next != null) {//	链表没到末尾
			//	让node指向下一个节点
			node = node.next;
		}
		//	node就是最后一个元素
		//	创建新的节点
		Node newNode = new Node();
		newNode.date = obj;
		//	新的节点加入到链表结构中
		node.next = newNode;
		//	个数+1
		size++;
	}
	/**	获得集合的元素个数*/
	public int size() {
		return size;
	}
	/**	从集合中获得指定位置(index)的元素*/
	public Object get(int index) {
		Node node = head;
		for(int i = 0; i <= index; i++) {
				node = node.next;
			}
			return node.date;
		}
	
	/**	向集合index的位置中插入obj元素*/
	public void add(int index,Object obj) {
		Node node = getPreNode(index);
		Node newNode = new Node();
		newNode.date = obj;
		//	新的节点加入到链表结构中
		newNode.next = node.next;
		node.next = newNode;
		//	个数+1
		size++;
	}
	/**	获得index位置的前置节点*/
	private Node getPreNode(int index) {
		Node node = head;
		for(int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}
	/**	删除指定位置(index)上的元素，并且返回删除的元素*/
	public Object remove(int index) {
		if(index >= size ||index < 0 ) {
			return null;
		}else {
		Node node = head;
		Object flag = null;
		for(int i = 0 ; i < index ; i++) {
			node = node.next;
		}
		flag = node.next.date;
		node.next = node.next.next;
		size--;
		return flag;
		}
		
	}
	/**	删除第一个指定元素(obj)*/
	public void remove(Object obj) {
		Node node = head;
		while(node.next != null) {
			if(node.date.equals(obj)) {
				node.next = node.next.next;
				size--;
				break;
		}
	}

		
	}
	/**	替换指定位置上的元素，替换成obj，并且返回被替换的元素*/
	public Object set(int index,Object obj) {
		Node node = getPreNode(index);
		Node newNode = new Node();
		Object o = newNode.date;
		newNode.date = obj;
		newNode.next = node.next.next;
		node.next = newNode;
		return o;
	}
	/**	判断集合中是否存在指定元素obj*/
	public boolean contain(Object obj) {
		Node node = head;
		boolean flag = false;
		loop:while(node.next != null) {
			node = node.next;
			if(node.date.equals(obj)) {
				flag = true;
				break loop;
			}
		}
		return flag;
	}
	/**	打印出项在集合中的有效元素*/
	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		Node node = head;
		while(node.next != null) {
			node = node.next;
			sb.append(node.date +", ");
		}
		sb.append("]");
		return sb.toString();
	}
}
